package main.java.LeetCode.ClassicalAlgorithm.Tree.Iterator;

import main.java.LeetCode.ClassicalAlgorithm.Tree.TreeIterator;
import main.java.LeetCode.CommonSolution.TreeNode;

import java.util.ArrayDeque;

public class InTreeIterator implements TreeIterator {
    private TreeNode cur;
    private final ArrayDeque<TreeNode> stack;

    public InTreeIterator(TreeNode root){
        this.cur = root;
        this.stack = new ArrayDeque<>();
    }

    @Override
    public int next(){
        while(cur!=null){
            stack.push(cur);
            cur = cur.left;
        }

        TreeNode now = stack.pop();
        cur = now.right;
        return now.val;
    }

    @Override
    public boolean hasNext(){
        return !(cur==null&&stack.isEmpty());
    }
}
